class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int n =  nums.size(),sum = 0;
            for(int i = 0 ; i < n ; i++) sum+=nums[i];
            if(sum%2 ==1) return false;
            int target = sum/2;
            vector<vector<int>> dp(n+1,vector<int>(target+1));
            //dp[i][j]表示数组0-i 的子序列能否凑齐和为 j
            dp[0][0] = true;
            for(int i = 1 ; i < n+1;i++) dp[i][0] = true;
            for(int i = 1 ; i < n+1 ; i++){
                for(int j = 1 ; j < target+1 ; j++){
                    //i位置选或者不选 取||
                    dp[i][j] = j-nums[i-1]>=0 ? dp[i-1][j] || dp[i-1][j-nums[i-1]] : dp[i-1][j];
                }
            }
            return dp[n][target];
        }
    };